package com.leetcode.partition11;

import java.io.*;
import java.util.ArrayList;
import java.util.List;

/**
 * @author `RKC`
 * @date 2021/12/26 18:57
 */
public class LC1012至少有1位重复的数字 {

    private static final int N = 11;
    //dp[i][j]表示的是i中选择j个的排列数，fact是用于求排列数的临时阶乘数组
    private static final long[][] dp = new long[N][N];
    private static final long[] fact = new long[N];

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(reader.readLine());
        init();
        writer.write(numDupDigitsAtMostN(n) + "\n");
        writer.flush();
    }

    private static void init() {
        fact[0] = 1;
        //预处理出来阶乘和组合数
        for (int i = 1; i < N; i++) fact[i] = fact[i - 1] * i;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j <= i; j++) {
                dp[i][j] = j == 0 ? 1 : dp[i - 1][j - 1] + dp[i - 1][j];
            }
        }
        //将组合数变成排列数
        for (int i = 0; i < N; i++) {
            for (int j = 0; j <= i; j++) {
                dp[i][j] *= fact[j];
            }
        }
    }

    /**
     * https://leetcode-cn.com/problems/numbers-with-repeated-digits/solution/shu-wei-dp-by-bruceyuj/
     * n=4567
     * 忽略最高位，也就是考虑最高位是0的情况
     * 4th 3th 2th 1th total
     *  0   0   0  1-9 9*A(9,0)
     *  0   0  1-9 0-9 9*A(9,1)
     *  0  1-9 0-9 0-9 9*A(9,2)
     *
     *  考虑上最高位的时候
     * 4th 3th 2th 1th total
     * 1-3 0-9 0-9 0-9 4*A(10-1,3)
     *  4  0-4 0-9 0-9 5*A(10-2,2)
     *  4   5  0-5 0-9 6*A(10-3,1)
     *  4   5   6  0-6 7*A(10-4,0)
     *  4   5   6   7  1
     */
    private static int numDupDigitsAtMostN(int n) {
        if (n <= 10) return 0;
        List<Integer> nums = new ArrayList<>();
        int num = n;
        while (num != 0) {
            nums.add(num % 10);
            num /= 10;
        }
        int answer = 0;
        int[] last = new int[10];
        //除去最高位i选择的情况，也就是不考虑最高位，相当于长度为nums.size()-1数的所有位的选择情况有 f(9,i-1)+f(9,i-2)+...+f(9,0)
        for (int i = 1; i < nums.size(); i++) answer += 9 * dp[9][i - 1];
        //有最高位的时候，后面的选择会受到对应位置的影响
        for (int i = nums.size() - 1; i >= 0; i--) {
            int x = nums.get(i);
            for (int j = i == nums.size() - 1 ? 1 : 0; j < x; j++) {
                if (last[j] != 0) continue;
                answer += dp[10 - (nums.size() - i)][i];
            }
            if (++last[x] > 1) break;
            //处理最后节点分支
            if (i == 0) answer++;
        }
        //全集减去没有任何一位重复的数字
        return n - answer;
    }
}
